#!/usr/bin/env python
# -*- encoding: utf-8 -*-
"""
@File    : shortest_path.py
@Time    : 2023/02/18 23:18:04
@Author  : 郭瑞强
@Contact : sunraing@126.com
@Version : 0.1
@License : BSD 3-Clause License
@Desc    : 图的最短路径问题
"""


from heapq import heapify, heappop, _siftdown
from .graph import Graph, Vertex
import sys


def dijkstra(graph: Graph, start: Vertex):
    # 利用 列表 与 heapq 库来模拟优先队列
    # 需要为 Vertex 重载 __lt__ 函数

    for vert in graph:
        vert.set_distance(sys.maxsize)
    start.set_distance(0)

    pq = [v for v in graph]
    heapify(pq)  # 初始化一个优先队列（小顶堆）

    while pq:
        cur_vert = heappop(pq)  # 取优先队列最前面的一个

        for next_vert in cur_vert.get_connections():
            new_dist = cur_vert.get_distance() + cur_vert.get_weight(next_vert)

            if new_dist < next_vert.get_distance():
                next_vert.set_pred(cur_vert)
                next_vert.set_distance(new_dist)  # 把该位置处调小，需要小值下沉操作

                pos = pq.index(next_vert)
                _siftdown(pq, 0, pos)  # 将小值向根处下沉
